package com.seven.leetcode.problems;

import java.util.Arrays;

/**
 * 88. 合并两个有序数组
 * MergeSortedArray
 * https://leetcode-cn.com/problems/merge-sorted-array/
 * 级别：Easy
 * <p>
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 * <p>
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
 * 输出：[1,2,2,3,5,6]
 * <p>
 * 示例 2：
 * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
 * 输出：[1]
 * <p>
 * [-1,0,0,3,3,3,0,0,0]  6
 * [1,2,2] 3
 * [-1,0,0,1,2,2,3,3,3]
 *
 * @author : wenguang
 * @date : 2021/4/02 10:42
 */
public class MergeSortedArray {

    public static void main(String[] args) {
        int m = 1;
        int[] nums1 = new int[]{4, 0, 0, 0, 0, 0};
        int[] nums2 = new int[]{1, 2, 3, 5, 6};
//        int m = 6;
//        int[] nums1 = new int[]{-1,0,0,3,3,3,0,0,0};
//        int[] nums2 = new int[]{1,2,2};
//        int m = 0;
//        int[] nums1 = new int[]{0};
//        int[] nums2 = new int[]{1};
        System.out.println("in: \nnums1:" + Arrays.toString(nums1) + " m: " + m +
            "\nnums2: " + Arrays.toString(nums2));
        merge1(nums1, m, nums2, nums2.length);
        System.out.println("out: " + Arrays.toString(nums1));
    }

    public static void merge1(int[] nums1, int m, int[] nums2, int n) {
        if (null == nums2 || 0 == n) {
            return;
        }

        if (m == 0) {
            System.arraycopy(nums2, 0, nums1, 0, n);
        } else {
            for (int i = n - 1; i >= 0; i--) {
                int num2 = nums2[i];
                int next = nums1[m - 1];
                if (num2 > next) {
                    nums1[m] = num2;
                } else {
                    int k = m;
                    while ((--k) >= 0 && nums1[k] > num2) {
                        nums1[k + 1] = nums1[k];
                    }
                    nums1[k + 1] = num2;
                }
                m++;
            }
        }
    }

    public static void merge2(int[] nums1, int m, int[] nums2, int n) {
        if (n >= 0) {
            System.arraycopy(nums2, 0, nums1, m, n);
        }

        Arrays.sort(nums1);
    }
}
